Skip to main content

Equivalence Relations

An equivalence relation on set on a set X is a relation ~ on the elements of X which satisfies the following properties:

  1. reflexive : ∀x∈X,x∼x\forall x \in X, x \sim x
  2. symmetric: ∀x∈X,∀y∈Y,x∼y  ⟹  y∼x\forall x \in X,\forall y \in Y, x \sim y \implies y \sim x
  3. transitive ∀x∈X,∀y∈Y,∀z∈Z,x∼y∧y∼z  ⟹  x∼z\forall x \in X, \forall y \in Y, \forall z \in Z, x \sim y \land y\sim z \implies x \sim z
  4. Equivalence class of xx is Ex={y∈X:y∼x}=xˉE_x = \{y\in X : y\sim x\} = \bar x

Partition: let subsets of a set xx notices by pp, the powerset of x by PP

  1. ⋃p∈P p=x\bigcup_{p\in P} \ p = x
  2. ∀p1,p2∈P,p1∧p2=∅\forall p_1, p_2 \in P, p_1 \land p_2 = \empty
  1. Two different equivalence class has no common elements
    1. assume two different equivalence class has common elements
    2. by transitivity, two class are the same
    3. contradiction with the assumption
  2. Modular has equivalence relation:
    1. ∀a∈Z,a≡a(mod m)\forall a \in \mathbb{Z}, a \equiv a (mod \ m)
      1. m∣a−am \mid a - a
    2. ∀a,b∈Z,a≡b(mod m)  ⟹  b≡a(mod m)\forall a,b \in \mathbb{Z}, a\equiv b (mod \ m) \implies b\equiv a (mod \ m)
      1. m∣a−b  ⟹  m∣b−am \mid a - b \implies m \mid b - a
    3. ∀a,b,c∈Z,a≡b(mod m)∧b≡c(mod m)  ⟹  a≡c(mod m)\forall a,b,c \in \mathbb{Z}, a\equiv b (mod \ m) \land b\equiv c (mod \ m) \implies a\equiv c (mod \ m)
      1. m∣a−b,m∣b−cm \mid a - b, m \mid b - c
      2. a−b=k1m,b−c=k2ma-b = k_1 m, b - c = k_2 m
      3. a−b+b−c=(k1+k2)ma-b+b-c = (k_1+k_2)m
      4. a≡c(mod m)a\equiv c (mod \ m)
    4. Ex={y∈Z:y≡x(mod m)}E_x = \{y\in \mathbb{Z} : y\equiv x (mod \ m)\}
  3. xˉ+yˉ={a+b:a+b≡x+y(mod m)}\bar x + \bar y = \{a+b : a+b\equiv x+y(mod \ m)\}
    1. a∈Z,b∈Z:a≡x(mod m),b≡y(mod m)a\in \mathbb{Z},b\in \mathbb{Z} : a\equiv x (mod \ m), b\equiv y (mod \ m)
  4. Similarly xˉ×yˉ={ab:ab≡xy(mod m)}\bar x \times \bar y = \{ab : ab\equiv xy(mod \ m)\}